package class11;

/**
 * https://leetcode.cn/problems/climbing-stairs/
 * 爬楼梯问题
 * 解题思路：
 * 斐波那契函数
 */
public class Code03_climbStairs {
    public static void main(String[] args) {

        int f = flip(20);
        System.out.println("f = " + f);
        int i = climbStairs(20);
        System.out.println("i = " + i);
    }

    public static int flip(int n) {
        int[] arr = new int[n + 1];
        int ans = f(n, arr);
        return ans;
    }

    public static int f(int i, int[] arr) {
        if (i <= 1) {
            return 1;
        }
        // 从数组中取值
        if (arr[i] != 0) {
            return arr[i];
        }
        int res = f(i - 1, arr) + f(i - 2, arr);
        // 将计算结果存到数组中
        arr[i] = res;
        return res;
    }

    /**
     * 使用迭代计算结果
     */
    public static int climbStairs(int n) {
        int i = 0, j = 1, ans = 0;
        for (int k = 0; k < n; k++) {
            ans = i + j;
            i = j;
            j = ans;
        }
        return ans;
    }
}
